package basic;

public class search {

    /**
     * 顺序查找
     * @param array
     * @param value
     * @return
     */
    private static int sequenceSearch(int[] array, int value) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == value) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 二分查找-非递归
     * @param arr
     * @param value
     * @return
     */
    private static int binarySearchFor(int[] arr, int value) {
        int head = 0;
        int tail = arr.length-1;
        int mid = (head+tail)/2;
        while (head <= tail) {
            mid = (head+tail)/2;
            if (arr[mid] < value) {
                head = mid+1;
            } else if (arr[mid] > value) {
                tail = mid-1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 二分查找-递归
     * @param arr
     * @param value
     * @return
     */
    private static int binarySearchRe(int[] arr, int value, int head, int tail) {
        int mid = head+(tail-head)/2;
        if (arr[mid] == value) {
            return mid;
        } else if (arr[mid] > value) {
            return binarySearchRe(arr, value, head, mid-1);
        } else {
            return binarySearchRe(arr, value, mid+1, tail);
        }
    }

    public static void main(String[] args) {
        System.out.println("basic search...");
//        int[] arr = new int[] {4,5,3,6,2,7,1,8,9,1};
//        System.out.println("1.sequence search....");
//        int res = sequenceSearch(arr, 1);
        int[] arr = new int[] {1,1,2,2,3,4,5,5,6,7,8,8,9};
        System.out.println("2.binary search....");
        int res = binarySearchFor(arr, 4);
        System.out.println("res:"+res);
        res = binarySearchRe(arr, 4, 0, arr.length);
        System.out.println("res:"+res);
    }

}
